// https://www.lintcode.com/problem/next-greater-element-i/description

class Solution {
public:
    /**
     * @param nums1: an array
     * @param nums2: an array
     * @return:  find all the next greater numbers for nums1's elements in the corresponding places of nums2
     */
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
        stack<int> record;
        vector<int> final;
        map<int, int> result;
        record.push(nums2.back());
        result[nums2.back()] = -1;
        for (int i = nums2.size() - 2; i >= 0; --i)
        {
            result[nums2[i]] = -1;
            if (!record.empty())
            {
                while (!record.empty() && nums2[i] > record.top())
                {
                    record.pop();
                }
                if (!record.empty()) result[nums2[i]] = record.top();
                record.push(nums2[i]);
            }
        }
        for (int i = 0; i < nums1.size(); ++i)
        {
            final.push_back(result[nums1[i]]);
        }
        return final;
    }
};